Self-complementary graph

A self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the 4-vertex path graph and the 5-vertex cycle graph.

Contents

Examples

Every Paley graph is self-complementary.[1] All strongly regular self-complementary graphs with fewer than 37 vertices are Paley graphs; however, there are strongly regular graphs on 37, 41, and 49 vertices that are not Paley graphs.[2]

The Rado graph is an infinite self-complementary graph.

Properties

An n-vertex self-complementary graph has exactly half number of edges of the complete graph, i.e., n(n − 1)/4 edges, and (if there is more than one vertex) it must have diameter either 2 or 3.[1] Since n(n −1) must be divisible by 4, n must be congruent to 0 or 1 mod 4; for instance, a 6-vertex graph cannot be self-complementary.

Computational complexity

Self-complementary graphs are interesting in their relation to the graph isomorphism problem: the problems of checking whether two self-complementary graphs are isomorphic and of checking whether a given graph is self-complementary are polynomial-time equivalent to the general graph isomorphism problem.[3]

References

  1. ^ a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen 9: 270–288, MR0151953 .
  2. ^ Rosenberg, I. G. (1982), "Regular and strongly regular selfcomplementary graphs", Theory and practice of combinatorics, North-Holland Math. Stud., 60, Amsterdam: North-Holland, pp. 223–238, MR806985 .
  3. ^ Colbourn, Marlene J.; Colbourn, Charles J. (1978), "Graph isomorphism and self-complementary graphs", SIGACT News 10 (1): 25–29, doi:10.1145/1008605.1008608 .